class Solution {
public:
    int tribonacci(int n) {
        // 1:动归
        // vector<int> dp(n + 1);

        // if (n == 0)
        //     return 0;
        // if (n == 1 || n == 2)
        //     return 1;

        // dp[0] = 0;
        // dp[1] = 1;
        // dp[2] = 1;

        // for (int i = 3; i <= n; i++) {
        //     // 状态转移方程
        //     dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        // }
        // //使用数组
        // return dp[n];



        //2:空间优化：滚动数组
        if(n == 0)return 0;
        if(n == 1|| n==2)return 1;
        int a,b,c,d;
        a=0;b=1;c=1;d=0;
        for(int i = 3;i<=n;i++){
            d = a+b+c;
            //滚动操作
            a=b;b=c;c=d;
        }
        return d;
    }
};
